Internet Surfer: Getting Started

home *** CD-ROM | disk | FTP | other *** search

/ Internet Surfer: Getting Started / Internet Surfer - Getting Started (Wayzata Technology)(7231)(1995).bin / pc / textfile / mac_faqs / puzz_faq / part02 < prev next >

Wrap

Internet Message Format | 1995-01-01 | 59.2 KB

Xref: bloom-picayune.mit.edu rec.puzzles:18137 news.answers:3069 Newsgroups: rec.puzzles,news.answers Path: bloom-picayune.mit.edu!enterpoop.mit.edu!snorkelwacker.mit.edu!usc!wupost!uunet!questrel!chris From: uunet!questrel!chris (Chris Cole) Subject: rec.puzzles FAQ, part 2 of 15 Message-ID: <puzzles-faq-2_717034101@questrel.com> Followup-To: rec.puzzles Summary: This posting contains a list of Frequently Asked Questions (and their answers). It should be read by anyone who wishes to post to the rec.puzzles newsgroup. Sender: chris@questrel.com (Chris Cole) Reply-To: uunet!questrel!faql-comment Organization: Questrel, Inc. References: <puzzles-faq-1_717034101@questrel.com> Date: Mon, 21 Sep 1992 00:08:31 GMT Approved: news-answers-request@MIT.Edu Expires: Sat, 3 Apr 1993 00:08:21 GMT Lines: 1579 Archive-name: puzzles-faq/part02 Last-modified: 1992/09/20 Version: 3 ==> analysis/bugs.p <== Four bugs are placed at the corners of a square. Each bug walks directly toward the next bug in the clockwise direction. The bugs walk with constant speed always directly toward their clockwise neighbor. Assuming the bugs make at least one full circuit around the center of the square before meeting, how much closer to the center will a bug be at the end of its first full circuit? ==> analysis/bugs.s <== Amorous Bugs ANSWER: 1 - e^(-2*pi) Let O(t) be the angle at time t of bug 1 relative to its starting point and r(O(t)) be its distance from the center of the square. Bug 1's vector trajectory is (using a Cartesian coordinate system with the origin at the center of the square): (1) X1 = [r(O) * cos(O), r(O) * sin(O)] By symmetry, bug 2's trajectory is the same only rotated by pi/2, viz.: (2) X2 = [-r(O) * sin(O), r(O) * cos(O)] Since bug 1 walks directly toward bug 2, the velocity of bug 1 must be proportional to the vector from bug 1 to bug 2: (3) d(X1)/d(t) = k * (X2 - X1) Equating each component of the vector equation (3) yields: (4) (d(r)/d(O) * cos(O) - r * sin(O)) * d(O)/d(t) = k * (-r * cos(O) - r * sin(O)) (5) (d(r)/d(O) * sin(O) + r * cos(O)) * d(O)/d(t) = k * (-r * sin(O) + r * cos(O)) These equations are solved by: (6) k = d(O)/d(t) and: (7) d(r)/d(O) = -r(O) (7) is solved by: (8) r(O) = e^-O Constant speed gives: (9) v^2 = constant = ((d(r)/d(O))^2+r^2)*(d(O)/d(t))^2 Substituting (8) into (9) yields (let V = v/sqrt(2)): (10) d(O)/d(t) = V * e^O Which is solved (using the boundary condition O(0) = 0) by: (11) O(t) = -ln(1 - V * t) Substituting (11) into (8) yields: (12) r(t) = r(0) - V * t The bug has made a full circle when O(T) = 2*pi; using (11): (13) T = 1/V * (1 - e^(-2*pi)) Substituting T into (12) yields the answer: (14) r(T) - r(0) = 1 - e^(-2*pi) ==> analysis/c.infinity.p <== What function is zero at zero, strictly positive elsewhere, infinitely differentiable at zero and has all zero derivitives at zero? ==> analysis/c.infinity.s <== exp(-1/x^2) This tells us why Taylor Series are a more limited device than they might be. We form a Taylor series by looking at the derivatives of a function at a given point; but this example shows us that the derivatives at a point may tell us almost nothing about its behavior away from that point. ==> analysis/cache.p <== Cache and Ferry (How far can a truck go in a desert?) A pick-up truck is in the desert beside N 50-gallon gas drums, all full. The truck's gas tank holds 10 gallons and is empty. The truck can carry one drum, whether full or empty, in its bed. It gets 10 miles to the gallon. How far away from the starting point can you drive the truck? ==> analysis/cache.s <== If the truck can siphon gas out of its tank and leave it in the cache, the answer is: { 1/1 + 1/3 + ... + 1/(2 * N - 1) } x 500 miles. Otherwise, the "Cache and Ferry" problem is the same as the "Desert Fox" problem described, but not solved, by Dewdney, July '87 "Scientific American". Dewdney's Oct. '87 Sci. Am. article gives for N=2, the optimal distance of 733.33 miles. In the Nov. issue, Dewdney lists the optimal distance of 860 miles for N=3, and gives a better, but not optimal, general distance formula. Westbrook, in Vol 74, #467, pp 49-50, March '90 "Mathematical Gazette", gives an even better formula, for which he incorrectly claims optimality: For N = 2,3,4,5,6: Dist = (600/1 + 600/3 + ... + 600/(2N-3)) + (600-100N)/(2N-1) For N > 6: Dist = (600/1 + 600/3 + ... + 600/9) + (500/11 + ... + 500/(2N-3)) The following shows that Westbrook's formula is not optimal for N=8: Ferry 7 drums forward 33.3333 miles (356.6667 gallons remain) Ferry 6 drums forward 51.5151 miles (300.0000 gallons remain) Ferry 5 drums forward 66.6667 miles (240.0000 gallons remain) Ferry 4 drums forward 85.7143 miles (180.0000 gallons remain) Ferry 3 drums forward 120.0000 miles (120.0000 gallons remain) Ferry 2 drums forward 200.0000 miles ( 60.0000 gallons remain) Ferry 1 drums forward 600.0000 miles --------------- Total distance = 1157.2294 miles (Westbrook's formula = 1156.2970 miles) ["Ferrying n drums forward x miles" involves (2*n-1) trips, each of distance x.] Other attainable values I've found: N Distance --- --------- (Ferry distances for each N are omitted for brevity.) 5 1016.8254 7 1117.8355 11 1249.2749 13 1296.8939 17 1372.8577 19 1404.1136 (The N <= 19 distances could be optimal.) 31 1541.1550 (I doubt that this N = 31 distance is optimal.) 139 1955.5509 (I'm sure that this N = 139 distance is not optimal.) So...where's MY formula? I haven't found one, and believe me, I've looked. I would be most grateful if someone would end my misery by mailing me a formula, a literature reference, or even an efficient algorithm that computes the optimal distance. If you do come up with the solution, you might want to first check it against the attainable distances listed above, before sending it out. (Not because you might be wrong, but just as a mere formality to check your work.) [Warning: the Mathematician General has determined that this problem is as addicting as Twinkies.] Myron P. Souris | "If you have anything to tell me of importance, McDonnell Douglas | for God's sake begin at the end." souris@mdcbbs.com | Sara Jeanette Duncan @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ The following output comes from some hack programs that I've used to empirically verify some proofs I've been working on. Initial barrels: 12 (600 gallons) Attainable distance= 1274.175211 Barrels Distance Gas Moved covered left >From depot 1: 10 63.1579 480.0000 >From depot 2: 8 50.0000 405.0000 >From depot 3: 7 37.5000 356.2500 >From depot 4: 6 51.1364 300.0000 >From depot 5: 5 66.6667 240.0000 >From depot 6: 4 85.7143 180.0000 >From depot 7: 3 120.0000 120.0000 >From depot 8: 2 200.0000 60.0000 >From depot 9: 1 600.0000 0.0000 Initial barrels: 40 (2000 gallons) Attainable distance= 1611.591484 Barrels Distance Gas Moved covered left >From depot 1: 40 2.5316 1980.0000 >From depot 2: 33 50.0000 1655.0000 >From depot 3: 28 50.0000 1380.0000 >From depot 4: 23 53.3333 1140.0000 >From depot 5: 19 50.0000 955.0000 >From depot 6: 16 56.4516 780.0000 >From depot 7: 13 50.0000 655.0000 >From depot 8: 11 54.7619 540.0000 >From depot 9: 9 50.0000 455.0000 >From depot 10: 8 32.1429 406.7857 >From depot 11: 7 38.9881 356.1012 >From depot 12: 6 51.0011 300.0000 >From depot 13: 5 66.6667 240.0000 >From depot 14: 4 85.7143 180.0000 >From depot 15: 3 120.0000 120.0000 >From depot 16: 2 200.0000 60.0000 >From depot 17: 1 600.0000 0.0000 ==> analysis/cats.and.rats.p <== If 6 cats can kill 6 rats in 6 minutes, how many cats does it take to kill one rat in one minute? ==> analysis/cats.and.rats.s <== The following piece by Lewis Carroll first appeared in ``The Monthly Packet'' of February 1880 and is reprinted in _The_Magic_of_Lewis_Carroll_, edited by John Fisher, Bramhall House, 1973. /Larry Denenberg larry@bbn.com larry@harvard.edu Cats and Rats If 6 cats kill 6 rats in 6 minutes, how many will be needed to kill 100 rats in 50 minutes? This is a good example of a phenomenon that often occurs in working problems in double proportion; the answer looks all right at first, but, when we come to test it, we find that, owing to peculiar circumstances in the case, the solution is either impossible or else indefinite, and needing further data. The 'peculiar circumstance' here is that fractional cats or rats are excluded from consideration, and in consequence of this the solution is, as we shall see, indefinite. The solution, by the ordinary rules of Double Proportion, is as follows: 6 rats : 100 rats \ > :: 6 cats : ans. 50 min. : 6 min. / . . . ans. = (100)(6)(6)/(50)(6) = 12 But when we come to trace the history of this sanguinary scene through all its horrid details, we find that at the end of 48 minutes 96 rats are dead, and that there remain 4 live rats and 2 minutes to kill them in: the question is, can this be done? Now there are at least *four* different ways in which the original feat, of 6 cats killing 6 rats in 6 minutes, may be achieved. For the sake of clearness let us tabulate them: A. All 6 cats are needed to kill a rat; and this they do in one minute, the other rats standing meekly by, waiting for their turn. B. 3 cats are needed to kill a rat, and they do it in 2 minutes. C. 2 cats are needed, and do it in 3 minutes. D. Each cat kills a rat all by itself, and take 6 minutes to do it. In cases A and B it is clear that the 12 cats (who are assumed to come quite fresh from their 48 minutes of slaughter) can finish the affair in the required time; but, in case C, it can only be done by supposing that 2 cats could kill two-thirds of a rat in 2 minutes; and in case D, by supposing that a cat could kill one-third of a rat in two minutes. Neither supposition is warranted by the data; nor could the fractional rats (even if endowed with equal vitality) be fairly assigned to the different cats. For my part, if I were a cat in case D, and did not find my claws in good working order, I should certainly prefer to have my one-third-rat cut off from the tail end. In cases C and D, then, it is clear that we must provide extra cat-power. In case C *less* than 2 extra cats would be of no use. If 2 were supplied, and if they began killing their 4 rats at the beginning of the time, they would finish them in 12 minutes, and have 36 minutes to spare, during which they might weep, like Alexander, because there were not 12 more rats to kill. In case D, one extra cat would suffice; it would kill its 4 rats in 24 minutes, and have 24 minutes to spare, during which it could have killed another 4. But in neither case could any use be made of the last 2 minutes, except to half-kill rats---a barbarity we need not take into consideration. To sum up our results. If the 6 cats kill the 6 rats by method A or B, the answer is 12; if by method C, 14; if by method D, 13. This, then, is an instance of a solution made `indefinite' by the circumstances of the case. If an instance of the `impossible' be desired, take the following: `If a cat can kill a rat in a minute, how many would be needed to kill it in the thousandth part of a second?' The *mathematical* answer, of course, is `60,000,' and no doubt less than this would *not* suffice; but would 60,000 suffice? I doubt it very much. I fancy that at least 50,000 of the cats would never even see the rat, or have any idea of what was going on. Or take this: `If a cat can kill a rat in a minute, how long would it be killing 60,000 rats?' Ah, how long, indeed! My private opinion is that the rats would kill the cat. ==> analysis/e.and.pi.p <== Which is greater, e^(pi) or (pi)^e ? ==> analysis/e.and.pi.s <== Put x = pi/e - 1 in the inequality e^x > 1+x (x>0). ==> analysis/functional/distributed.p <== Find all f: R -> R, f not identically zero, such that (*) f( (x+y)/(x-y) ) = ( f(x)+f(y) )/( f(x)-f(y) ). ==> analysis/functional/distributed.s <== 1) Assuming f finite everywhere, (*) ==> x<>y ==> f(x)<>f(y) 2) Exchanging x and y in (*) we see that f(-x) = -f(x). 3) a <> 0 ==> f((a-a)/(a+a)) = (f(a)-f(a))/(f(a)+f(a)) ==> f(0) = 0. 4) a <> 0 ==> f((a+0)/(a-0)) = f(a)/f(a) ==> f(1) = 1. 5) x<>y, y<>0 ==> f(x/y) = f( ((x+y)/(x-y) + (x-y)/(x-y)) / ((x+y)/(x-y) - (x-y)/(x-y)) = f(x)/f(y) ==> f(xy) = f(x)f(y) by replacing x with xy and by noting that f(x*1) = f(x)*1 and f(x*0) = f(x)*f(0). 6) f(x*x) = f(x)*f(x) ==> f(x) > 0 if x>0. 7) Let a=1+\/2, b=1-\/2; a,b satisfy (x+1)/(x-1) = x ==> f(x) = (f(x)+1)/(f(x)-1) ==> f(a)=a, f(b)=b. f(1/\/2) = f((a+b)/(a-b)) = (a+b)/(a-b) = 1/\/2 ==> f(2) = 2. 8) By induction and the relation f((n+1)/(n-1)) = (f(n)+1)/(f(n)-1) we get that f(n)=n for all integer n. #5 now implies that f fixes the rationals. 9) If x>y>0 (*) ==> f(x) - f(y) = f(x+y)/f((x+y)/(x-y)) > 0 by #6. Thus f is order-preserving. Since f fixes the rationals *and* f is order-preserving, f must be the identity function. This was E2176 in _The American Mathematical Monthly_ (the proposer was R. S. Luthar). ==> analysis/functional/linear.p <== Suppose f is non-decreasing with f(x+y) = f(x) + f(y) + C for all real x, y. Prove: there is a constant A such that f(x) = Ax - C for all x. (Note: continuity of f is not assumed in advance.) ==> analysis/functional/linear.s <== By induction f(mx) = m(f(x)+C)-C. Let x=1/n, m=n and find that f(1/n) = (1/n)(f(1)+C)-C. Now let x=1/n and find that f(m/n) = (m/n)(f(1)+C)-C. f(-x+x) = f(-x) + f(x) + C ==> f(-x) = -2C - f(x) (since f(0) = -C) ==> f(-m/n) = -(m/n)(f(1)+C)-C. Since f is monotonic ==> f(x) = x*(f(1)+C)-C for all real x (Squeeze Theorem). ==> analysis/integral.p <== If f is integrable on (0,inf), and differentiable at 0, and a > 0, show: inf ( f(x) - f(ax) ) Int ---------------- dx = f(0) ln(a) 0 x ==> analysis/integral.s <== First, note that if f(0) is 0, then by substituting u=ax in the integral of f(x)/x, our integral is the difference of two equal integrals and so is 0 (the integrals are finite because f is 0 at 0 and differentiable there. Note I make no requirement of continuity). Second, note that if f is the characteristic function of the interval [0, 1]--- i.e. 1, 0<=x<=1 f (x) = 0 otherwise then a little arithmetic reduces our integral to that of 1/x from 1/a to 1 (assuming a>1; if a <= 1 the reasoning is similar), which is ln(a) = f(0)ln(a) as required. Call this function g. Finally, note that the operator which takes the function f to the value of our integral is linear, and that every function meeting the hypotheses (incidentally, I should have said `differentiable from the right', or else replaced the characteristic function of [0,1] above by that of (-infinity, 1]; but it really doesn't matter) is a linear combination of one which is 0 at 0 and g, to wit f(x) = f(0)g(x) + (f(x) - g(x)f(0)). ==> analysis/period.p <== What is the least possible integral period of the sum of functions of periods 3 and 6? ==> analysis/period.s <== Period 2. Clearly, the sum of periodic functions of periods 2 and three is 6. So take the function which is the sum of that function of period six and the negative of the function of period three and you have a function of period 2. ==> analysis/rubberband.p <== A bug walks down a rubberband which is attached to a wall at one end and a car moving away from the wall at the other end. The car is moving at 1 m/sec while the bug is only moving at 1 cm/sec. Assuming the rubberband is uniformly and infinitely elastic, will the bug ever reach the car? ==> analysis/rubberband.s <== Let w = speed of bug and N = ratio of car speed/bug speed = 100. Paint N+1 equally spaced stripes on the rubberband. When the bug is standing on one stripe, the next stripe is moving away from him at a speed slightly < w (relative to him). Since he is walking at w, clearly the bug can reach the next stripe. But once he reaches that stripe, the next one is only receeding at < w. So he walks on down to the car, one stripe at a time. The bug starts gaining on the car when he is at the next to last stripe. ==> analysis/series.p <== Show that in the series: x, 2x, 3x, .... (n-1)x (x can be any real number) there is at least one number which is within 1/n of an integer. ==> analysis/series.s <== Throw 0 into the sequence; there are now n numbers, so some pair must have fractional parts within 1/n of each other; their difference is then within 1/n of an integer. ==> analysis/snow.p <== Snow starts falling before noon on a cold December day. At noon a snowplow starts plowing a street. It travels 1 mile in the first hour, and 1/2 mile in the second hour. What time did the snow start falling?? You may assume that the plow's rate of travel is inversely proportioned to the height of the snow, and that the snow falls at a uniform rate. ==> analysis/snow.s <== 11:22:55.077 am. Method: Let b = the depth of the snow at noon, a = the rate of increase in the depth. Then the depth at time t (where noon is t=0) is at+b, the snowfall started at t_0=-b/a, and the snowplow's rate of progress is ds/dt = k/(at+b). If the snowplow starts at s=0 then s(t) = (k/a) log(1+at/b). Note that s(2 hours) = 1.5 s(1 hour), or log(1+2A/b) = 1.5 log(1+A/b), where A = (1 hour)*a. Letting x = A/b we have (1+2x)^2 = (1+x)^3. Solve for x and t_0 = -(1 hour)/x. The exact answer is 11:(90-30 Sqrt[5]). _American Mathematics Monthly_, April 1937, page 245 E 275. Proposed by J. A. Benner, Lafayette College, Easton. Pa. The solution appears, appropriately, in the December 1937 issue, pp. 666-667. Also solved by William Douglas, C. E. Springer, E. P. Starke, W. J. Taylor, and the proposer. See R.P. Agnew, "Differential Equations," 2nd edition, p. 39 ff. ==> analysis/tower.p <== A number is raised to its own power. The same number is then raised to the power of this result. The same number is then raised to the power of this second result. This process is continued forever. What is the maximum number which will yield a finite result from this process? ==> analysis/tower.s <== Tower of Exponentials ANSWER: e^(1/e) Let N be the number in question and R the result of the process. Then R can be defined recursively by the equation: (1) R = N^R Taking the logarithm of both sides of (1): (2) ln(R) = R * ln(N) Dividing (2) by R and rearranging: (3) ln(N) = ln(R) / R Exponentiating (3): (4) N = R^(1/R) We wish to find the maximum value of N with respect to R. Find the derivative of N with respect to R and set it equal to zero: (5) d(N)/d(R) = (1 - ln(R)) / R^2 = 0 For finite values of R, (5) is satisfied by R = e. This is a maximum of N if the second derivative of N at R = e is less than zero. (6) d2(N)/d2(R) | R=e = (2 * ln(R) - 3) / R^3 | R=e = -1 / e^3 < 0 The solution therefore is (4) at R = e: (7) Nmax = e^(1/e) ==> arithmetic/7-11.p <== A customer at a 7-11 store selected four items to buy, and was told that the cost was $7.11. He was curious that the cost was the same as the store name, so he inquired as to how the figure was derived. The clerk said that he had simply multiplied the prices of the four individual items. The customer protested that the four prices should have been ADDED, not MULTIPLIED. The clerk said that that was OK with him, but, the result was still the same: exactly $7.11. What were the prices of the four items? ==> arithmetic/7-11.s <== The prices are: $1.20, $1.25, $1.50, and $3.16 $7.11 is not the only number which works. Here are the first 160 such numbers, preceded by a count of distinct solutions for that price. Note that $7.11 has a single, unique solution. 1 - $6.44 1 - $7.83 2 - $9.20 3 - $10.89 1 - $6.51 1 - $7.86 1 - $9.23 1 - $10.95 1 - $6.60 3 - $7.92 1 - $9.24 2 - $11.00 1 - $6.63 1 - $8.00 1 - $9.27 1 - $11.07 1 - $6.65 1 - $8.01 2 - $9.35 1 - $11.13 1 - $6.72 1 - $8.03 3 - $9.36 1 - $11.16 2 - $6.75 5 - $8.10 1 - $9.38 1 - $11.22 1 - $6.78 1 - $8.12 5 - $9.45 2 - $11.25 1 - $6.80 1 - $8.16 2 - $9.48 2 - $11.27 2 - $6.84 2 - $8.19 1 - $9.54 1 - $11.30 1 - $6.86 1 - $8.22 1 - $9.57 1 - $11.36 1 - $6.89 1 - $8.25 1 - $9.59 1 - $11.40 2 - $6.93 3 - $8.28 2 - $9.60 2 - $11.43 1 - $7.02 3 - $8.33 1 - $9.62 2 - $11.52 1 - $7.05 1 - $8.36 2 - $9.63 2 - $11.55 2 - $7.07 1 - $8.37 1 - $9.66 2 - $11.61 1 - $7.08 2 - $8.40 1 - $9.68 1 - $11.69 1 - $7.11 1 - $8.45 2 - $9.69 1 - $11.70 1 - $7.13 2 - $8.46 1 - $9.78 1 - $11.88 2 - $7.14 1 - $8.52 2 - $9.80 1 - $11.90 3 - $7.20 5 - $8.55 1 - $9.81 1 - $11.99 1 - $7.25 1 - $8.60 1 - $9.87 1 - $12.06 1 - $7.26 4 - $8.64 4 - $9.90 1 - $12.15 2 - $7.28 1 - $8.67 1 - $9.92 1 - $12.18 1 - $7.29 1 - $8.69 2 - $9.99 1 - $12.24 3 - $7.35 1 - $8.73 1 - $10.01 1 - $12.30 1 - $7.37 2 - $8.75 1 - $10.05 1 - $12.32 1 - $7.47 1 - $8.76 2 - $10.08 1 - $12.35 1 - $7.50 1 - $8.78 1 - $10.17 2 - $12.42 1 - $7.52 5 - $8.82 1 - $10.20 1 - $12.51 4 - $7.56 1 - $8.85 2 - $10.26 1 - $12.65 1 - $7.62 1 - $8.88 3 - $10.29 2 - $12.69 4 - $7.65 2 - $8.91 3 - $10.35 1 - $12.75 1 - $7.67 1 - $8.94 2 - $10.44 1 - $12.92 2 - $7.70 1 - $8.96 1 - $10.53 1 - $12.96 3 - $7.74 3 - $9.00 1 - $10.56 1 - $13.23 1 - $7.77 1 - $9.02 1 - $10.64 1 - $13.41 1 - $7.79 2 - $9.03 2 - $10.71 1 - $13.56 2 - $7.80 1 - $9.12 3 - $10.80 1 - $14.49 1 - $7.82 2 - $9.18 1 - $10.85 1 - $15.18 There are plenty of solutions for five summands. Here are a few: $8.28 -- at least two solutions $8.47 -- at least two solutions $8.82 -- at least two solutions -- Mark Johnson mark@microunity.com (408) 734-8100 There may be many approximate solutions, for example: $1.01, $1.15, $2.41, and $2.54. These sum to $7.11 but the product is 7.1100061. ==> arithmetic/clock/day.of.week.p <== It's restful sitting in Tom's cosy den, talking quietly and sipping a glass of his Madeira. I was there one Sunday and we had the usual business of his clock. When the radio gave the time at the hour, the Ormolu antique was exactly 3 minutes slow. "It loses 7 minutes every hour", my old friend told me, as he had done so many times before. "No more and no less, but I've gotten used to it that way." When I spent a second evening with him later that same month, I remarked on the fact that the clock was dead right by radio time at the hour. It was rather late in the evening, but Tom assured me that his treasure had not been adjusted nor fixed since my last visit. What day of the week was the second visit? From "Mathematical Diversions" by Hunter + Madachy ==> arithmetic/clock/day.of.week.s <== The answer is 17 days and 3 hours later, which would have been a Wednesday. This is the only other time in the same month when the two would agree at all. In 17 days the slow clock loses 17*24*7 minutes = 2856 minutes, or 47 hours and 36 minutes. In 3 hours more it loses 21 minutes, so it has lost a total of 47 hours and 57 minutes. Modulo 12 hours, it has *gained* 3 minutes so as to make up the 3 minutes it was slow on Sunday. It is now (fortnight plus 3 days) exactly accurate. ==> arithmetic/clock/thirds.p <== Do the 3 hands on a clock ever divide the face of the clock into 3 equal segments, i.e. 120 degrees between each hand? ==> arithmetic/clock/thirds.s <== First let us assume that our clock has 60 divisions. We will show that any time the hour hand and the minute hand are 20 divisions (120 degrees) apart, the second hand cannot be an integral number of divisions from the other hands, unless it is straight up (on the minute). Let us use h for hours, m for minutes, and s for seconds. We will use =n to mean congruent mod n, thus 12 =5 7. We know that m =60 12h, that is, the minute hand moves 12 times as fast as the hour hand, and wraps around at 60. We also have s =60 60m. This simplifies to s/60 =1 m, which goes to s/60 = frac(m) (assuming s is in the range 0 <= s < 60), which goes to s = 60 frac(m). Thus, if m is 5.5, s is 30. Now let us assume the minute hand is 20 divisions ahead of the hour hand. So m =60 h + 20, thus 12h =60 h + 20, 11h =60 20, and, finally, h =60/11 20/11 (read 'h is congruent mod 60/11 to 20/11'). So all values of m are k + n/11 for some integral k and integral n, 0 <= n < 11. s is therefore 60n/11. If s is to be an integral number of units from m and h, we must have 60n =11 n. But 60 and 11 are relatively prime, so this holds only for n = 0. But if n = 0, m is integral, so s is 0. Now assume, instead, that the minute hand is 20 divisions behind the hour hand. So m =60 h - 20, 12h =60 h - 20, 11h =60 -20, h =60/11 -20/11. So m is still k + n/11. Thus s must be 0. But if s is 0, h must be 20 or 40. But this translates to 4 o'clock or 8 o'clock, at both of which the minute hand is at 0, along with the second hand. Thus the 3 hands can never be 120 degrees apart, Q.E.D. ==> arithmetic/consecutive.product.p <== Prove that the product of three or more consecutive natural numbers cannot be a perfect square. ==> arithmetic/consecutive.product.s <== Three consecutive numbers: If a and b are relatively prime, and ab is a square, then a and b are squares. (This is left as an exercise.) Suppose (n - 1)n(n + 1) = k^2, where n > 1. Then n(n^2 - 1) = k^2. But n and (n^2 - 1) are relatively prime. Therefore n^2 - 1 is a perfect square, which is a contradiction. Four consecutive numbers: n(n + 1)(n + 2)(n + 3) = (n^2 + 3n + 1)^2 - 1 Five consecutive numbers: Assume the product is a integer square, call it m. The prime factorization of m must have even numbers of each prime factor. For each prime factor, p, of m, p >= 5, p^2k must divide one of the consecutive naturals in the product. (Otherwise, the difference between two of the naturals in the product would be a positive multiple of a prime >= 5. But in this problem, the greatest difference is 4.) So we need only consider the primes 2 and 3. Each of the consecutive naturals is one of: 1) a perfect square 2) 2 times a perfect square 3) 3 times a perfect square 4) 6 times a perfect square. By the shoe box principle, two of the five consecutive numbers must fall into the same category. If there are two perfect squares, then their difference being less than five limits their values to be 1 and 4. (0 is not a natural number, so 0 and 1 and 0 and 4 cannot be the perfect squares.) But 1*2*3*4*5=120!=x*x where x is an integer. If there are two numbers that are 2 times a perfect square, then their difference being less than five implies that the perfect squares (which are multiplied by 2) are less than 3 apart, and no two natural squares differ by only 1 or 2. A similar argument holds for two numbers which are 3 times a perfect square. We cannot have the case that two of the 5 consecutive numbers are multiples (much less square multiples) of 6, since their difference would be >= 6, and our span of five consecutive numbers is only 4. Therefore the assumption that m is a perfect square does not hold. QED. In general the equation: y^2 = x(x+1)(x+2)...(x+n), n > 3 has only the solution corresponding to y = 0. This is a theorem of Rigge [O. Rigge, ``Uber ein diophantisches Problem'', IX Skan. Math. Kong. Helsingfors (1938)] and Erdos [P. Erdos, ``Note on products of consecutive integers,'' J. London Math. Soc. #14 (1939), pages 194-198]. A proof can be found on page 276 of [L. Mordell, ``Diophantine Equations'', Academic Press 1969]. ==> arithmetic/consecutive.sums.p <== Find all series of consecutive positive integers whose sum is exactly 10,000. ==> arithmetic/consecutive.sums.s <== Generalize to find X (and I) such that (X + X+1 + X+2 + ... + X+I) = T for any integer T. You are asking for all (X,I) s.t. (2X+I)(I+1) = 2T. The problem is (very) slightly easier if we don't restrict X to being positive, so we'll solve this first. Note that 2X+I and I+1 must have different parities, so the answer to the relaxed question is N = 2*(o_1+1)*(o_2+1)*...*(o_n+1), where 2T = 2^o_0*3^o_1*...*p_n^o_n (the prime factorization); this is easily seen to be the number of ways we can break 2T up into two positive factors of differing parity (with order). In particular, 20000 = 2^5*5^4, hence there are 2*(4+1) = 10 solutions for T = 10000. These are (2X+I,I+1): (32*1,5^4) (32*5,5^3) (32*5^2,5^2) (32*5^3,5) (32*5^4,1) (5^4,32*1) (5^3,32*5) (5^2,32*5^2) (5,32*5^3) (1,32*5^4) And they give rise to the solutions (X,I): (-296,624) (28,124) (388,24) (1998,4) (10000,0) (297,31) (-27,179) (-387,799) (-1997,3999) (-9999,19999) If you require that X>0 note that this is true iff 2X+I > I+1 and hence the number of solutions to this problem is N/2 (due to the symmetry of the above ordered pairs). ==> arithmetic/digits/all.ones.p <== Prove that some multiple of any integer ending in 3 contains all 1s. ==> arithmetic/digits/all.ones.s <== Let n be our integer; one such desired multiple is then ( 10^(phi(n))-1 )/9. All we need is that (n,10) = 1, and if the last digit is 3 this must be the case. A different proof using the pigeonhole principle is to consider the sequence 1, 11, 111, ..., (10^n - 1)/9. By previous reasoning we must have at some point that either some member of our sequence = 0 (mod n) or else some value (mod n) is duplicated. Assume the latter, with x_a and x_b, x_b>x_a, possesing the duplicated remainders. We then have that x_b - x-a = 0 (mod n). Let m be the highest power of 10 dividing x_b - x_a. Now since (10,n) = 1, we can divide by 10^m and get that (x_b - x_a)/10^m = 0 (n). But (x_b - x_a)/10^m is a number containing only the digit 1. Q.E.D. ==> arithmetic/digits/arabian.p <== What is the Arabian Nights factorial, the number x such that x! has 1001 digits? How about the prime x such that x! has exactly 1001 zeroes on the tail end. (Bonus question, what is the 'rightmost' non-zero digit in x!?) ==> arithmetic/digits/arabian.s <== The first answer is 450!. Determining the number of zeroes at the end of x! is relatively easy once you realize that each such zero comes from a factor of 10 in the product 1 * 2 * 3 * ... * x Each factor of 10, in turn, comes from a factor of 5 and a factor of 2. Since there are many more factors of 2 than factors of 5, the number of 5s determines the number of zeroes at the end of the factorial. The number of 5s in the set of numbers 1 .. x (and therefore the number of zeroes at the end of x!) is: z(x) = int(x/5) + int(x/25) + int(x/125) + int(x/625) + ... This series terminates when the powers of 5 exceed x. I know of no simple way to invert the above formula (i.e., to find x for a given z(x)), but I can approximate it by noting that, except for the "int" function, 5*z(x) - x = z(x) which gives: x = 4*z(x) (approximately). The given problem asked, "For what prime x is z(x)=1001". By the above forumla, this is approximately 4*1001=4004. However, 4004! has only 800 + 160 + 32 + 6 + 1 = 999 zeroes at the end of it. The numbers 4005! through 4009! all have 1000 zeroes at their end and the numbers 4010! through 4014! all have 1001 zeroes at their end. Since the problem asked for a prime x, and 4011 = 3*7*191, the only solution is x=4013. The problem of determining the rightmost nonzero digit in x! is somewhat more difficult. If we took the numbers 1, 2, ... , x and removed all factors of 5 (and an equal number of factors of 2), the remaining numbers multiplied together modulo 10 would be the answer. Note that since there are still many factors of 2 left, the rightmost nonzero digit must be 2, 4, 6, or 8 (x > 1). Letting r(x) be the rightmost nonzero digit in x!, an expression for r(x) is: r(x) = (r(int(x/5)) * w * r(x mod 10)) mod 10, x >= 10. where w is 4 if int(x/10) is odd and 6 if it is even. The values of r(x) for 0 <= x <= 9 are 1, 1, 2, 6, 4, 2, 2, 4, 2, and 8. The way to see this is true is to take the numbers 1, 2, ..., x in groups of 10. In each group, remove 2 factors of 10. For example, from the set 1, 2, ..., 10, choose a factor of 2 from 2 and 6 and a factor of 5 from 5 and 10. This leaves 1, 1, 3, 4, 1, 3, 7, 8, 9, 2. Next, separate all the factors that came from multiples of 5. The rightmost nonzero digit of x! can now (hopefully) be seen to be: r(x) = (r(int(x/5)) * w * r(x mod 10)) mod 10 where w is the rightmost digit in the number formed by multiplying the numbers 1, 2, 3, ..., 10*int(x/10) after the factors of 10 and the factors left over by the multiples of 5 have been removed. In the example with x = 10, this would be (1 * 1 * 3 * 4 * 3 * 7 * 8 * 9) mod 10 = 4. The "r(x mod 10)" term takes care of the numbers from 10*int(x/10)+1 up to x. The "w" term can be seen to be 4 or 6 depending on whether int(x/10) is odd or even since, after removing 10*n+5 and 10*n+10 and a factor of 2 each from 10*n+2 and 10*n+6 from the group of numbers 10*n+1 through 10*n+10, the remaining factors (mod 10) always equals 4 and 4^t mod 10 = 4 if t is odd and 6 when t is even (t != 0). So, finally, the rightmost nonzero digit in 4013! is found as follows: r(4013) = (r(802) * 4 * 6) mod 10 r(802) = (r(160) * 6 * 2) mod 10 r(160) = (r(32) * 6 * 1) mod 10 r(32) = (r(6) * 4 * 2) mod 10 Using a table of r(x) for 0 <= x <= 9, r(6) = 2. Then, r(32) = (2 * 4 * 2) mod 10 = 6 r(160) = (6 * 6 * 1) mod 10 = 6 r(802) = (6 * 6 * 2) mod 10 = 2 r(4013) = (2 * 4 * 6) mod 10 = 8 Thus, the rightmost nonzero digit in 4013! is 8. ==> arithmetic/digits/circular.p <== What 6 digit number, with 6 different digits, when multiplied by all integers up to 6, circulates its digits through all 6 possible positions, as follows: ABCDEF * 1 = ABCDEF ABCDEF * 3 = BCDEFA ABCDEF * 2 = CDEFAB ABCDEF * 6 = DEFABC ABCDEF * 4 = EFABCD ABCDEF * 5 = FABCDE ==> arithmetic/digits/circular.s <== ABCDEF=142857 (the digits of the expansion of 1/7). ==> arithmetic/digits/divisible.p <== Find the least number using 0-9 exactly once that is evenly divisible by each of these digits? ==> arithmetic/digits/divisible.s <== Since the sum of the digits is 45, any permutation of the digits gives a multiple of 9. To get a multiple of both 2 and 5, the last digit must be 0, and thus to get a multiple of 8 (and 4), the tens digit must be even, and the hundreds digit must be odd if the tens digit is 2 or 6, and even otherwise. The number will also be divisible by 6, since it is divisible by 2 and 3, so 7 is all we need to check. First, we will look for a number whose first five digits are 12345; now, 1234500000 has a remainder of 6 when divided by 7, so we have to arrange the remaining digits to get a remainder of 1. The possible arrangements, in increasing order, are 78960, remainder 0 79680, remainder 6 87960, remainder 5 89760, remainder 6 97680, remainder 2 98760, remainder 4 That didn't work, so try numbers starting with 12346; this is impossible because the tens digit must be 8, and the hundreds digit cannot be even. Now try 12347, and 1234700000 has remainder 2. The last five digits can be 58960, remainder 6 59680, remainder 5, so this works, and the number is 1234759680. ==> arithmetic/digits/equations/123456789.p <== In how many ways can "." be replaced with "+", "-", or "" (concatenate) in .1.2.3.4.5.6.7.8.9=1 to form a correct equation? ==> arithmetic/digits/equations/123456789.s <== 1-2 3+4 5+6 7-8 9 = 1 +1-2 3+4 5+6 7-8 9 = 1 1+2 3+4-5+6 7-8 9 = 1 +1+2 3+4-5+6 7-8 9 = 1 -1+2 3-4+5+6 7-8 9 = 1 1+2 3-4 5-6 7+8 9 = 1 +1+2 3-4 5-6 7+8 9 = 1 1-2 3-4+5-6 7+8 9 = 1 +1-2 3-4+5-6 7+8 9 = 1 1-2-3-4 5+6 7-8-9 = 1 +1-2-3-4 5+6 7-8-9 = 1 1+2-3 4+5 6-7-8-9 = 1 +1+2-3 4+5 6-7-8-9 = 1 -1+2 3+4+5-6-7-8-9 = 1 -1 2+3 4-5-6+7-8-9 = 1 1+2+3+4-5+6+7-8-9 = 1 +1+2+3+4-5+6+7-8-9 = 1 -1+2+3-4+5+6+7-8-9 = 1 1-2-3+4+5+6+7-8-9 = 1 +1-2-3+4+5+6+7-8-9 = 1 1+2 3+4 5-6 7+8-9 = 1 +1+2 3+4 5-6 7+8-9 = 1 1+2 3-4-5-6-7+8-9 = 1 +1+2 3-4-5-6-7+8-9 = 1 1+2+3+4+5-6-7+8-9 = 1 +1+2+3+4+5-6-7+8-9 = 1 -1+2+3+4-5+6-7+8-9 = 1 1-2+3-4+5+6-7+8-9 = 1 +1-2+3-4+5+6-7+8-9 = 1 -1-2-3+4+5+6-7+8-9 = 1 1-2+3+4-5-6+7+8-9 = 1 +1-2+3+4-5-6+7+8-9 = 1 1+2-3-4+5-6+7+8-9 = 1 +1+2-3-4+5-6+7+8-9 = 1 -1-2+3-4+5-6+7+8-9 = 1 -1+2-3-4-5+6+7+8-9 = 1 -1+2 3+4 5-6 7-8+9 = 1 1-2 3-4 5+6 7-8+9 = 1 +1-2 3-4 5+6 7-8+9 = 1 -1+2 3-4-5-6-7-8+9 = 1 -1+2+3+4+5-6-7-8+9 = 1 1-2+3+4-5+6-7-8+9 = 1 +1-2+3+4-5+6-7-8+9 = 1 1+2-3-4+5+6-7-8+9 = 1 +1+2-3-4+5+6-7-8+9 = 1 -1-2+3-4+5+6-7-8+9 = 1 1+2-3+4-5-6+7-8+9 = 1 +1+2-3+4-5-6+7-8+9 = 1 -1-2+3+4-5-6+7-8+9 = 1 -1+2-3-4+5-6+7-8+9 = 1 1-2-3-4-5+6+7-8+9 = 1 +1-2-3-4-5+6+7-8+9 = 1 1-2 3+4+5+6+7-8+9 = 1 +1-2 3+4+5+6+7-8+9 = 1 1+2+3+4 5-6 7+8+9 = 1 +1+2+3+4 5-6 7+8+9 = 1 1 2+3 4+5-6 7+8+9 = 1 +1 2+3 4+5-6 7+8+9 = 1 1+2+3-4-5-6-7+8+9 = 1 +1+2+3-4-5-6-7+8+9 = 1 -1+2-3+4-5-6-7+8+9 = 1 1-2-3-4+5-6-7+8+9 = 1 +1-2-3-4+5-6-7+8+9 = 1 -1-2-3-4-5+6-7+8+9 = 1 -1-2 3+4+5+6-7+8+9 = 1 1-2+3 4-5 6+7+8+9 = 1 +1-2+3 4-5 6+7+8+9 = 1 1 2-3 4+5-6+7+8+9 = 1 +1 2-3 4+5-6+7+8+9 = 1 Total solutions = 69 69/19683 = 0.35 % for those who care (it's not very elegant but it did the trick): #include <stdio.h> #include <math.h> main (argc,argv) int argc; char *argv[]; { int sresult, result, operator[10],thisop; char buf[256],ops[3]; int i,j,tot=0,temp; ops[0] = ' '; ops[1] = '-'; ops[2] = '+'; for (i=1; i<10; i++) operator[i] = 0; for (j=0; j < 19683; j++) { result = 0; sresult = 0; thisop = 1; for (i=1; i<10; i++) { switch (operator[i]) { case 0: sresult = sresult * 10 + i; break; case 1: result = result + sresult * thisop; sresult = i; thisop = -1; break; case 2: result = result + sresult * thisop; sresult = i; thisop = 1; break; } } result = result + sresult * thisop; if (result == 1) { tot++; for (i=1;i<10;i++) printf("%c%d",ops[operator[i]],i); printf(" = %d\n",result); } temp = 0; operator[1] += 1; for (i=1;i<10;i++) { operator[i] += temp; if (operator[i] > 2) { operator[i] = 0; temp = 1;} else temp = 0; } } printf("Total solutions = %d\n" , tot); } cwren@media.mit.edu (Christopher Wren) ==> arithmetic/digits/equations/1992.p <== 1 = -1+9-9+2. Extend this list to 2 - 100 on the left side of the equals sign. ==> arithmetic/digits/equations/1992.s <== 1 = -1+9-9+2 2 = 1*9-9+2 3 = 1+9-9+2 4 = 1+9/9+2 5 = 1+9-sqrt(9)-2 6 = 1^9+sqrt(9)+2 7 = -1+sqrt(9)+sqrt(9)+2 8 = 19-9-2 9 = (1/9)*9^2 10= 1+(9+9)/2 11= 1+9+sqrt(9)-2 12= 19-9+2 13= (1+sqrt(9))!-9-2 14= 1+9+sqrt(9)!-2 15= -1+9+9-2 16= -1+9+sqrt(9)!+2 17= 1+9+9-2 18= 1+9+sqrt(9)!+2 19= -1+9+9+2 20= (19-9)*2 21= 1+9+9+2 22= (-1+sqrt(9))*(9-2) 23= (1+sqrt(9))!-sqrt(9)+2 24= -1+9*sqrt(9)-2 25= 1*9*sqrt(9)-2 26= 19+9-2 27= 1*9+9*2 28= 1+9+9*2 29= 1*9*sqrt(9)+2 30= 19+9+2 31= (1+sqrt(9))!+9-2 32= -1+sqrt(9)*(9+2) 33= 1*sqrt(9)*(9+2) 34= (-1+9+9)*2 35= -1+(9+9)*2 36= 1^9*sqrt(9)!^2 37= 19+9*2 38= 1*sqrt(9)!*sqrt(9)!+2 39= 1+sqrt(9)!*sqrt(9)!+2 40= (1+sqrt(9)!)*sqrt(9)!-2 41= -1+sqrt(9)!*(9-2) 42= (1+sqrt(9))!+9*2 43= 1+sqrt(9)!*(9-2) 44= -1+9*(sqrt(9)+2) 45= 1*9*(sqrt(9)+2) 46= 1+9*(sqrt(9)+2) 47= (-1+sqrt(9)!)*9+2 48= 1*sqrt(9)!*(sqrt(9)!+2) 49= (1+sqrt(9)!)*(9-2) 50= (-1+9)*sqrt(9)!+2 51= -1+9*sqrt(9)!-2 52= 1*9*sqrt(9)!-2 53= -1+9*sqrt(9)*2 54= 1*9*sqrt(9)*2 55= 1+9*sqrt(9)*2 56= 1*9*sqrt(9)!+2 57= 1+9*sqrt(9)!+2 58= (1+9)*sqrt(9)!-2 59= 19*sqrt(9)+2 60= (1+9)*sqrt(9)*2 61= (1+sqrt(9)!)*9-2 62= -1+9*(9-2) 63= 1*9*(9-2) 64= 1+9*(9-2) 65= (1+sqrt(9)!)*9+2 66= 1*sqrt(9)!*(9+2) 67= 1+sqrt(9)!*(9+2) 68= -(1+sqrt(9))!+92 69= (1+sqrt(9))!+(9/.2) 70= (1+9)*(9-2) 71= -1-9+9^2 72= (1+sqrt(9))*9*2 73= -19+92 74= (-1+9)*9+2 75= -1*sqrt(9)!+9^2 76= 1-sqrt(9)!+9^2 77= (1+sqrt(9)!)*(9+2) 78= -1+9*9-2 79= 1*9*9-2 80= 1+9*9-2 81= 1*9*sqrt(9)^2 82= -1+9*9+2 83= 1*9*9+2 84= 1+9*9+2 85= -1-sqrt(9)!+92 86= -1*sqrt(9)!+92 87= 1-sqrt(9)!+92 88= (1+9)*9-2 89= -1*sqrt(9)+92 90= 1-sqrt(9)+92 91= -1^9+92 92= (1+9)*9+2 93= 1^9+92 94= -1+sqrt(9)+92 95= 19*(sqrt(9)+2) 96= -1+99-2 97= 1*99-2 98= 1+99-2 99= 1*9*(9+2) 100= -1+99+2 ==> arithmetic/digits/equations/383.p <== Make 383 out of 1,2,25,50,75,100 using +,-,*,/. ==> arithmetic/digits/equations/383.s <== You can get 383 with ((2+50)/25+1)*100+75. Of course, if you expect / as in C, the above expression is just 375. But then you can get 383 with (25*50-100)/(1+2). Pity there's no way to use the 75. If we had a language that rounded instead of truncating, we could use ((1+75+100)*50)/(25-2) or (2*75*(25+100))/(50-1). I imagine your problem lies in not dividing things that aren't divisible. Dan Hoey Hoey@AIC.NRL.Navy.Mil ==> arithmetic/digits/extreme.products.p <== What are the extremal products of three three-digit numbers using digits 1-9? ==> arithmetic/digits/extreme.products.s <== There is a simple procedure which applies to these types of problems (and which can be proven with help from the arithmetic-geometric inequality). For the first part we use the "first large then equal" procedure. This means that are three numbers will be 7**, 8**, and 9**. Now the digits 4,5,6 get distributed so as to make our three number as close to each other as possible, i.e. 76*, 85*, 94*. The same goes for the remaining three digits, and we get 763, 852, 941. For the second part we use the "first small then different" procedure. Our three numbers will be of the form 1**, 2**, 3**. We now place the three digits so as to make our three numbers as unequal as possible; this gives 14*, 25*, 36*. Finishing, we get 147, 258, 369. Now, *prove* that these procedures work for generalizations of this problem. ==> arithmetic/digits/googol.p <== What digits does googol! start with? ==> arithmetic/digits/googol.s <== I'm not sure how to calculate the first googol of digits of log10(e), but here's the first 150(approximately) of them... 0.43429448190325182765112891891660508229439700580366656611445378316586464920 8870774729224949338431748318706106744766303733641679287158963906569221064663 We need to deal with the digits immediately after the decimal point in googol*log10(e), which are .187061 frac[log(googol!)] = frac[halflog2pi + 50 + googol(100-log10(e))] = frac{halflog2pi + frac[googol(100-log10(e))]} = frac[.399090 + (1- .187061)] = .212029 10 ** .212029 = 1.629405 Which means that googol! starts with 1629 ==> arithmetic/digits/labels.p <== You have an arbitrary number of model kits (which you assemble for fun and profit). Each kit comes with twenty (20) stickers, two of which are labeled "0", two are labeled "1", ..., two are labeled "9". You decide to stick a serial number on each model you assemble starting with one. What is the first number you cannot stick. You may stockpile unused numbers on already assembled models, but you may not crack open a new model to get at its stickers. You complete assembling the current model before starting the next. ==> arithmetic/digits/labels.s <== The method I used for this problem involved first coming up with a formula that says how many times a digit has been used in all n models. n = k*10^i + m for some k,m with 0 <k <10, m < 10^i f(d,n) = (number of d's used getting to k*10^i from digits 0 to (i-1)) + (number of d's used by #'s 10^i to n from digit i) + f(d,m) f(d,n) = i*k*10^(i-1) + (if (d < k) 10^i else if (d == k) m+1 else 0) + f(d,m) This doesn't count 0's, which should be ok as they are not used as often as other digits. From the formula, it is clear that f(1,n) is never less than f(d,n) for 1<d<10. So I just calculated f(1,n) for various n (with some help from bc). I quickly discovered that for n = 2*10^15, f(1,n) = 2*n. After further trials I determined that for n = 1999919999999981, f(1,n) = 2*n + 1. This appears to be the smallest n with f(1,n) > 2*n. ==> arithmetic/digits/nine.digits.p <== Form a number using 0-9 once with its first n digits divisible by n. ==> arithmetic/digits/nine.digits.s <== First, reduce the sample set. For each digit of ABCDEFGHI, such that the last digit, (current digit), is the same as a multiple of N : A: Any number 1-9 B: Even numbers 2,4,6,8 (divisible by 2). C: Any number 1-9 (21,12,3,24,15,6,27,18,9). D: Even numbers 2,4,6,8 (divisible by 4, every other even). E: 5 (divisible by 5 and 0 not allowed). F: Even numbers (12,24,6,18) G: Any number 1-9 (21,42,63,14,35,56,7,28,49). H: Even numbers (32,24,16,8) I: Any number 1-9 (81,72,63,54,45,36,27,18,9) Since E must be 5, I can eliminate it everywhere else. Since I will use up all the even digits, (2,4,6,8) filling in those spots that must be even. Any number becomes all odds, except 5. A: 1,3,7,9 B: 2,4,6,8 C: 1,3,7,9 D: 2,4,6,8 E: 5 F: 2,4,6,8 G: 1,3,7,9 H: 2,4,6,8 I: 1,3,7,9 We have that 2C+D=0 (mod 4), and since C is odd, this implies that D is 2 or 6; similarly we find that H is 2 or 6 ==> {B,F} = {4,8}. D+5+F=0 (mod 3) ==> if D=2 then F=8, if D=6 then F=4. We have two cases. Assume our number is of the form A4C258G6I0. Now the case n=8 ==> G=1,9; case n=3 ==> A+1+C=0 (mod 3) ==> {A,C}={1,7} ==> G=9, I=3. The two numbers remaining fail for n=7. Assume our number is of the form A8C654G2I0. The case n=8 ==> G=3,7. If G=3, we need to check to see which of 1896543, 9816543, 7896543, and 9876543 are divisible by 7; none are. If G=7, we need to check to see which of 1896547, 9816547, 1836547, and 3816547 are divisible by 7; only the last one is, which yields the solution 3816547290. ==> arithmetic/digits/palindrome.p <== Does the series formed by adding a number to its reversal always end in a palindrome? ==> arithmetic/digits/palindrome.s <== This is not known. If you start with 196, after 9480000 iterations you get a 3924257-digit non-palindromic number. However, there is no known proof that you will never get a palindrome. The statement is provably false for binary numbers. Roland Sprague has shown that 10110 starts a series that never goes palindromic. ==> arithmetic/digits/palintiples.p <== Find all numbers that are multiples of their reversals. ==> arithmetic/digits/palintiples.s <== We are asked to find numbers that are integer multiples of their reversals, which I call palintiples. Of course, all the palindromic numbers are a trivial example, but if we disregard the unit multiples, the field is narrowed considerably. Rouse Ball (_Mathematical_recreations_and_essays_) originated the problem, and G. H. Hardy (_A_mathematician's_apology_) used the result that 9801 and 8712 are the only four-digit palintiples as an example of a theorem that is not ``serious''. Martin Beech (_The_mathema- tical_gazette_, Vol 74, #467, pp 50-51, March '90) observed that 989*01 and 879*12 are palintiples, an observation he ``confirmed'' on a hand calculator, and conjectured that these are all that exist. I confirm that Beech's numbers are palintiples, I will show that they are not all of the palintiples. I will show that the palintiples do not form a regular language. And then I will prove that I have found all the palintiples, by describing the them with a generalized form of regular expression. The results become more interesting in other bases. First, I have a more reasonable method of confirming that these numbers are palintiples: Proof: First, letting "9*" and "0*" refer an arbitrary string of nines and a string of zeroes of the same length, I note that 879*12 = 879*00 + 12 = (880*00 - 100) + 12 = 880*00 - 88 219*78 = 219*00 + 78 = (220*00 - 100) + 78 = 220*00 - 22 989*01 = 989*00 + 1 = (990*00 - 100) + 1 = 990*00 - 99 109*89 = 109*00 + 89 = (110*00 - 100) + 89 = 110*00 - 11 It is obvious that 4x(220*00 - 22) = 880*00 - 88 and that 9x(110*00 - 11) = 990*00 - 99. QED. Now, to show that these palintiples are not all that exist, let us take the (infinite) language L[4] = (879*12 + 0*), and let Pal(L[4]) refer to the set of palindromes over the alphabet L[4]. It is immediate that the numbers in Pal(L[4]) are palintiples. For instance, 8712 000 87912 879999912 879999912 87912 000 8712 = 4 x 2178 000 21978 219999978 219999978 21978 000 2178 (where I have inserted spaces to enhance readability) is a palintiple. Similarly, taking L[9] = (989*01 + 0*), the numbers in Pal(L[9]) are palintiples. We exclude numbers starting with zeroes. The reason these do not form a regular language is that the sub-palintiples on the left end of the number must be the same (in reverse order) as the sub-palintiples on the right end of the number: 8712 8712 87999912 = 4 x 2178 2178 21999978 is not a palintiple, because 8712 8712 87999912 is not the reverse of 2178 2178 21999978. The pumping lemma can be used to prove that Pal(L[4])+Pal(L[9]) is not a regular language, just as in the familiar proof that the palindromes over a non-singleton alphabet do not form a regular language. Now to characterize all the palintiples, let N be a palintiple, N=CxR(N), where R(.) signifies reversal, and C>1 is an integer. (I use "x" for multiplication, to avoid confusion with the Kleene star "*", which signifies the concatenated closure.) If D is a digit of N, let D' refer to the corresponding digit of R(N). Since N=CxR(N), D+10T = CxD'+S, where S is the carry in to the position occupied by D' when R(N) is multiplied by C, and T is the carry out of that position. Similarly, D'+10T'=CxD+S', where S', T' are carries in and out of the position occupied by D when R(N) is multiplied by C. Since D and D' are so closely related, I will use the symbol D:D' to refer to a digit D on the left side of a string with a corresponding digit D' on the right side of the string. More formally, an expression "x[1]:y[1] x[2]:y[2] ... x[n]:y[n] w" will refer to a string "x[1] x[2] ... x[n] w y[n] ... y[2] y[1]", where the x[i] and y[i] are digits and w is a string of zero or one digits. So 989901 may be written as 9:1 8:0 9:9 and 87912 may be written as 8:2 7:1 9. Thus Pal(L[4])+Pal(L[9]) (omitting numbers with leading zeroes) can be represented as (8:2 7:1 9:9* 1:7 2:8 0:0*)* (0:0* + 0 + 8:2 7:1 ( 9:9* + 9:9* 9)) + (9:1 8:0 9:9* 0:8 1:9 0:0*)* (0:0* + 0 + 9:1 8:0 ( 9:9* + 9:9* 9)). (1) For each pair of digits D:D', there are a very limited--and often empty--set of quadruples S,T,S',T' of digits that satisfy the equations D +10T =CxD'+S D'+10T'=CxD +S', (2) yet such a quadruple must exist for "D:D'" to appear in a palintiple with multiplier C. Furthermore, the S and T' of one D:D' must be T and S', respectively, of the next pair of digits that appear. This enables us to construct a finite state machine to recognize those palintiples. The states [X#Y] refer to a pair of carries in D and D', and we allow a transition from state [T#S'] to state [S#T'] on input symbol D:D' exactly when equations (2) are satisfied. Special transitions for a single-digit input symbol (the central digit of odd-length palintiples) and the criteria for the initial and the accepting states are left as exercises. The finite state machines thus formed are State Symbol New Symbol New Symbol New Accept? State State State --> [0#0] Y 8:2 [0#3] 0:0 [0#0] 0 [A] [0#3] N 7:1 [3#3] [3#3] Y 1:7 [3#0] 9:9 [3#3] 9 [A] [3#0] N 2:8 [0#0] [A] Y for constant C=4, and State Symbol New Symbol New Symbol New Accept? State State State --> [0#0] Y 1:9 [0#8] 0:0 [0#0] 0 [A] [0#8] N 8:0 [8#8] [8#8] Y 0:8 [8#0] 9:9 [8#8] 9 [A] [8#0] N 9:1 [0#0] [A] Y for constant C=9, and the finite state machines for other constants accept only strings of zeroes. It is not hard to verify that the proposed regular expression (1) represents the union of the languages accepted by these machines, omitting the empty string and strings beginning with zero. I have written a computer program that constructs finite state machines for recognizing palintiples for various bases and constants. I found that base 10 is actually an unusually boring base for this problem. For instance, the machine for base 8, constant C=5 is State Symbol New Symbol New Symbol New Accept? State State State --> [0#0] Y 0:0 [0#0] 5:1 [0#3] 0 [A] [0#3] N 1:0 [1#1] 6:1 [1#4] [1#1] Y 0:1 [3#0] 5:2 [3#3] [3#0] N 1:5 [0#0] 6:6 [0#3] 6 [A] [3#3] Y 2:5 [1#1] 7:6 [1#4] [1#4] N 1:1 [4#1] 6:2 [4#4] 1 [A] [4#4] Y 2:6 [4#1] 7:7 [4#4] 7 [A] [4#1] N 1:6 [3#0] 6:7 [3#3] [A] Y for which I invite masochists to write the regular expression. If anyone wants more, I should remark that the base 29 machine for constant C=18 has 71 states! By the way, I did not find any way of predicting the size or form of the machines for the various bases, except that the machines for C=B-1 all seem to be isomorphic to each other. If anyone investigates the general behavior, I would be most happy to hear about it. Dan Hoey Hoey@AIC.NRL.Navy.Mil May, 1992 [ A preliminary version of this message appeared in April, 1991. ] ================================================================ Dan ==> arithmetic/digits/power.two.p <== Prove that for any 9-digit number (base 10) there is an integral power of 2 whose first 9 digits are that number. ==> arithmetic/digits/power.two.s <== Let v = log to base 10 of 2. Then v is irrational. Let w = log to base 10 of these 9 digits. Since v is irrational, given epsilon > 0, there exists some natural number n such that {w} < {nv} < {w} + epsilon ({x} is the fractional part of x.) Let us pick n for when epsilon = log 1.00000000000000000000001. Then 2^n does the job. ==> arithmetic/digits/prime/101.p <== How many primes are in the sequence 101, 10101, 1010101, ...? ==> arithmetic/digits/prime/101.s <== Note that the sequence 101 , 10101, 1010101, .... can be viewed as 100**1 +1, 100**2 + 100**1 + 1, 100**3 + 100**2 + 100**1 +1 .... that is, the k-th term in the sequence is 100**k + 100**(k-1) + 100**(k-2) + ...+ 100**(1) + 1 = (100)**(k+1) - 1 ---------------- 11 * 9 = (10)**(2k+2) - 1 ---------------- 11 * 9 = ((10)**(k+1) - 1)*((10)**(k+1) +1) --------------------------------- 11*9 thus either 11 and 9 divide the numerator. Either they both divide the same factor in the numerator or different factors in the numerator. In any case, after dividing, they leave the numerators as a product of two integers. Only in the case of k = 1, one of the integers is 1. Thus there is exactly one prime in the above sequence: 101. ==> arithmetic/digits/prime/all.prefix.p <== What is the longest prime whose every proper prefix is a prime? ==> arithmetic/digits/prime/all.prefix.s <== 23399339, 29399999, 37337999, 59393339, 73939133 ==> arithmetic/digits/prime/change.one.p <== What is the smallest number that cannot be made prime by changing a single digit? Are there infinitely many such numbers? ==> arithmetic/digits/prime/change.one.s <== 200. Obviously, you would have to change the last digit, but 201, 203, 207, and 209 are all composite. For any smaller number, you can change the last digit, and get 2,11,23,31,41,53,61,71,83,97,101,113,127,131,149,151,163,173,181, or 191. 200+2310n gives an infinite family, because changing the last digit to 1 or 7 gives a number divisible by 3; to 3, a number divisible by 7; to 9, a number divisible by 11. ==> arithmetic/digits/prime/prefix.one.p <== 2 is prime, but 12, 22, ..., 92 are not. Similarly, 5 is prime whereas 15, 25, ..., 95 are not. What is the next prime number which is composite when any digit is prefixed? ==> arithmetic/digits/prime/prefix.one.s <== 149 ==> arithmetic/digits/reverse.p <== Is there an integer that has its digits reversed after dividing it by 2? ==> arithmetic/digits/reverse.s <== Assume there's such a positive integer x such that x/2=y and y is the reverse of x. Then x=2y. Let x = a...b, then y = b...a, and: b...a (y) x 2 -------- a...b (x) From the last digit b of x, we have b = 2a (mod 10), the possible values for b are 2, 4, 6, 8 and hence possible values for (a, b) are (1,2), (6,2), (2,4), (7,4), (3,6), (8,6), (4,8), (9,8). From the first digit a of x, we have a = 2b or a = 2b+1. None of the above pairs satisfy this condition. A contradiction. Hence there's no such integer. ==> arithmetic/digits/rotate.p <== Find integers where multiplying them by single digits rotates their digits. ==> arithmetic/digits/rotate.s <== 2 105263157894736842 3 1034482758620689655172413793 4 102564 153846 179487 205128 230769 5 142857 102040816326530612244897959183673469387755 6 1016949152542372881355932203389830508474576271186440677966 1186440677966101694915254237288135593220338983050847457627 1355932203389830508474576271186440677966101694915254237288 1525423728813559322033898305084745762711864406779661016949 7 1014492753623188405797 1159420289855072463768 1304347826086956521739 8 1012658227848 1139240506329 9 10112359550561797752808988764044943820224719 In base B, suppose you have an N-digit answer A whose digits are rotated when multiplied by K. If D is the low-order digit of A, we have (A-D)/B + D B^(N-1) = K A . Solving this for A we have D (B^N - 1) A = ----------- . B K - 1 In order for A >= B^(N-1) we must have D >= K. Now we have to find N such that B^N-1 is divisible by R=(BK-1)/gcd(BK-1,D). This always has a minimal solution N0(R,B)<R, and the set of all solutions is the set of multiples of N0(R,B). N0(R,B) is the length of the repeating part of the fraction 1/R in base B. N0(ST,B)=N0(S,B)N0(T,B) when (S,T)=1, and for prime powers, N0(P^X,B) divides (P-1)P^(X-1). Determining which divisor is a little more complicated but well-known (cf. Hardy & Wright). So given B and K, there is one minimal solution for each D=K,K+1,...,B-1, and you get all the solutions by taking repetitions of the minimal solutions. ==> arithmetic/digits/sesqui.p <== Find the least number where moving the first digit to the end multiplies by 1.5.